package com.lw.leetcode.arr.c;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 37. 解数独
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/21 17:26
 */
public class SolveSudoku {

    public void solveSudoku(char[][] matrix) {
        bb(matrix, 0, 0);
    }

    public boolean bb(char[][] matrix, int x, int y) {
        if (x == 8 && y == 9) {
            return true;
        }
        if (y == 9) {
            y = 0;
            x++;
        }
        if (matrix[x][y] != '.') {
            return bb(matrix, x, y + 1);
        }
        boolean flag = false;
        List<Character> cc = cc(matrix, x, y);
        if (cc.size() == 0) {
            return flag;
        }
        for (Character cter : cc) {
            matrix[x][y] = cter;
            if (bb(matrix, x, y + 1)) {
                return true;
            } else {
                matrix[x][y] = '.';
            }
        }
        return flag;
    }


    public List<Character> cc(char[][] matrix, int x, int y) {
        List<Character> list = new ArrayList<>(8);
        byte[] arr = new byte[9];
        for (int i = 0; i < 9; i++) {
            if (matrix[x][i] != '.') {
                arr[matrix[x][i] - 49] = 1;
            }
            if (matrix[i][y] != '.') {
                arr[matrix[i][y] - 49] = 1;
            }
        }
        int i = x / 3 * 3;
        int j = y / 3 * 3;
        for (int k = 0; k < 3; k++) {
            for (int m = 0; m < 3; m++) {
                if (matrix[k + i][m + j] != '.') {
                    arr[matrix[k + i][m + j] - 49] = 1;
                }
            }
        }
        for (int k = 0; k < 9; k++) {
            if (arr[k] != 1) {
                list.add((char) (k + 49));
            }
        }
        return list;
    }
}
